/*
Algorithms:  brief Definition of algorithms classes from thrust to fui.
    Copyright (C) 2012  Jorge E. A. Atala
                        FuDePAN
    This file is part of the Fui Proyect.

    Fui is free software: you can redistribute it and/or modify
    it under the terms of the GNU General Public License as published by
    the Free Software Foundation, either version 3 of the License, or
    (at your option) any later version.

    Fui is distributed in the hope that it will be useful,
    but WITHOUT ANY WARRANTY; without even the implied warranty of
    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
    GNU General Public License for more details.

    You should have received a copy of the GNU General Public License
    along with Fui.  If not, see <http://www.gnu.org/licenses/>.
*/

#ifndef GENERAL_ALGORITHMS_H
#   define GENERAL_ALGORITHMS_H
#   include<cassert>
namespace fui
{
/*! \addtogroup Algorithms
 *  \addtogroup For
 *  \ingroup Algorithms
 *  \{
 */

/*!
 *  \p SideBySidePolicy is a policy that define how the elements will be
 *  obtained from the vectors source in the /p For algorithm.
 *  In this case, the policy is take an element from the first vector
 *  and an element from the second vector which has the same index of the
 *  first one. Then, put the result of the binary operation in the same
 *  index position on the result vector.
 *
 *  \code
 *  ...
 *  struct PlusOperation
 *  {
 *      __host__ __device__
 *      int operator()(int a, int b)
 *      {
 *          return a + b;
 *      }
 *  };
 *
 *
 *  fui::device_vector<int>::type data1(6,1);
 *  fui::device_vector<int>::type data2(6,2);
 *  fui::device_vector<int>::type result(6);
 *  fui::For<SideBySidePolicy> looper;
 *  looper.run(data1.begin(), data1.end(), data2.begin(), data2.end(), result.begin(), PlusOperation());
 *
 *  // result == {3,3,3,3,3,3}
 *  \endcode
 *
 *  \see For
 */
class SideBySidePolicy
{
protected:
    /*! \cond
     */
    template<class InputIterator1 , class InputIterator2 , class OutputIterator , class BinaryFunction>
    void doLoop(InputIterator1 firstBegin, const InputIterator1 firstLast,
                InputIterator2 secondBegin, const InputIterator2 secondLast,
                OutputIterator result, BinaryFunction op)
    {
        const unsigned int firstSize = firstLast - firstBegin;
        const unsigned int secondSize = secondLast - secondBegin;
        assert(firstSize == secondSize);
        fui::transform(firstBegin, firstLast, secondBegin, result, op);
    }
    /*! \endcond
     */
};

/*! \p OneToAllPolicy is a policy that define how the elements will be
 *  obtained from the vectors source in the /p For algorithm.
 *  In this case, the policy is take an element from the first vector
 *  and applied the operation with all the elements on the second vector
 *. Then, put the result of the binary operation secuentially in the
 *  result vector
 *
 *  \code
 *  ...
 *  struct PlusOperation
 *  {
 *      __host__ __device__
 *      int operator()(int a, int b)
 *      {
 *          return a + b;
 *      }
 *  };
 *
 *
 *  fui::counting_iterator<int>::type first(1);
 *  fui::counting_iterator<int>::type last = first + 3;
 *  // {1,2,3,4}
 *  fui::device_vector<int>::type result(16);
 *  fui::For<OnetoAllPolicy> looper;
 *  looper.run(data1.begin(), data1.end(), data1.begin(), data1.end(), result.begin(), PlusOperation());
 *
 *  // result == { 2 , 3 , 4 , 5 , 3 , 4 , 5 , 6 , 4 , 5 , 6 , 7 , 5 , 6 , 7 , 8 }
 *  //             |   |   |   |   |   |   |   |   |   |   |   |   |   |   |   |
 *  // result == {1+1,1+2,1+3,1+4,2+1,2+2,2+3,2+4,3+1,3+2,3+3,3+4,4+1,4+2,4+3,4+4}
 *  \endcode
 *
 *  \see For
 */
class OneToAllPolicy
{
protected:
    /*! \cond
     */
    template<class InputIterator1 , class InputIterator2 , class OutputIterator , class BinaryFunction>
    void doLoop(InputIterator1 firstBegin, const InputIterator1 firstLast,
                InputIterator2 secondBegin, const InputIterator2 secondLast,
                OutputIterator result, BinaryFunction op)
    {
        const unsigned int firstSize = firstLast - firstBegin;
        const unsigned int secondSize = secondLast - secondBegin;
        fui::transform
        (
            fui::make_permutation_iterator(firstBegin, fui::make_transform_iterator(
                                               fui::make_counting_iterator<unsigned int>(0), fui::FirstIndexOTA(secondSize))),
            fui::make_permutation_iterator(firstBegin, fui::make_transform_iterator(
                                               fui::make_counting_iterator<unsigned int>(0),
                                               fui::FirstIndexOTA(secondSize))) + firstSize * secondSize,
            fui::make_permutation_iterator(secondBegin, fui::make_transform_iterator(
                                               fui::make_counting_iterator<unsigned int>(0), fui::SecondtIndexOTA(secondSize))),
            result,
            op
        );
    }
    /*! \endcond
     */
};


/*! \p OneToLeftPolicy is a policy that define how the elements will be
 *  obtained from the vectors source in the /p For algorithm.
 *  In this case, the policy is take an element from the first vector
 *  and applied the operation with all the elements on the second vector
 *  who has an index strict greater than it. Then, put the result of
 *  the binary operation secuentially in the result vector.
 *
 *  \code
 *  ...
 *  struct PlusOperation
 *  {
 *      __host__ __device__
 *      int operator()(int a, int b)
 *      {
 *          return a + b;
 *      }
 *  };
 *
 *
 *  fui::counting_iterator<int>::type first(1);
 *  fui::counting_iterator<int>::type last = first + 3;
 *  // {1,2,3,4}
 *  fui::device_vector<int>::type result(6);
 *  fui::For<OnetoLeftPolicy> looper;
 *  looper.run(data1.begin(), data1.end(), data1.begin(), data1.end(), result.begin(), PlusOperation());
 *
 *  // result == { 3 , 4 , 5 , 5 , 6 , 7 }
 *  //             |   |   |   |   |   |
 *  // result == {1+2,1+3,1+4,2+3,2+4,3+4}
 *  \endcode
 *
 *  \see For
 */
class OneToLeftPolicy : public Combinator
{

protected:
    /*! \cond
     */
    template<class InputIterator1 , class InputIterator2 , class OutputIterator , class BinaryFunction>
    void doLoop(InputIterator1 firstBegin, const InputIterator1 firstLast,
                InputIterator2 secondBegin, const InputIterator2 secondLast,
                OutputIterator result, BinaryFunction op)
    {
        const unsigned int firstSize = firstLast - firstBegin;
        const unsigned int secondSize = secondLast - secondBegin;
        unsigned int totalSize = summatoria(firstSize - 1);
        assert(firstSize == secondSize);
        fui::transform
        (
            fui::make_permutation_iterator(firstBegin, fui::make_transform_iterator(
                                               fui::make_counting_iterator<unsigned int>(0), fui::FirstIndexOTL(firstSize - 1))),
            fui::make_permutation_iterator(firstBegin, fui::make_transform_iterator(
                                               fui::make_counting_iterator<unsigned int>(0),
                                               fui::FirstIndexOTL(firstSize - 1))) + totalSize,
            fui::make_permutation_iterator(secondBegin, fui::make_transform_iterator(
                                               fui::make_counting_iterator<unsigned int>(0), fui::SecondtIndexOTL(secondSize - 1))),
            result,
            op
        );
    }

    template<class InputIterator, class OutputIterator , class CombinatorialFunction>
    void doLoop(InputIterator begin,
                const InputIterator last,
                OutputIterator result,
                CombinatorialFunction op,
                size_t combinations)
    {
        const unsigned int vecSize = last - begin;
        assert(combinations <= vecSize);
        size_t outputSize = vecSize;

        if (combinations >= 2)
            outputSize += summatoria(vecSize - 1);
        /* first method
        for(size_t i = 2; i<combinations;++i)
            for(size_t j = i; j<vecSize;++j)
                outputSize += summatoria(vecSize - j);
        */

        /* second method
        for(size_t i = 1; i<=vecSize -2;++i)
        {
            size_t j = vecSize - 1 - i;
            outputSize += summatoria(j) * std::min(i,(combinations-2));
        }
        */

        //third method
        size_t sum = 0;
        for (size_t i = 1; i <= vecSize - 2; ++i)
        {
            sum += i;
            outputSize += sum * std::min((vecSize - 1 - i), (combinations - 2));
        }
        std::cout << "magic number" << outputSize << std::endl;




    }
    /*! \endcond
     */

};


/*! \p For, is a class that can make an operation with the elements of two
 *  vectors sequentially, and put the result on the third vector.
 *  The order in each element will be taken from inputs vectors depends to
 *  the \p Policy selected.
 */
template<class Policy>
class For : public Policy
{
public:

    /*! when call \p run method, the loop starts, following the order determinated
     *  for the \p Policy selected.
     *
     *  \param firstBegin The beginning of the first sequence.
     *  \param firstLast The end of the first sequence.
     *  \param secondBegin The beginning of the second sequence.
     *  \param secondLast The end of the second sequence.
     *  \param result The beginning of the result sequence.
     *  \param op The binary operation which will be applied over the inputs elements.
     *
     *  The following code snippet demonstrates how to use the \p For algorithm.
     *
     *  \code
     *  ...
     *  struct PlusOperation
     *  {
     *      __host__ __device__
     *      int operator()(int a, int b)
     *      {
     *          return a + b;
     *      }
     *  };
     *
     *
     *  fui::device_vector<int>::type data1(6,1);
     *  fui::device_vector<int>::type data2(6,2);
     *  fui::device_vector<int>::type result(6);
     *  fui::For<fui::SideBySide> looper;
     *  looper.run(data1.begin(), data1.end(), data2.begin(), data2.end(), result.begin(), PlusOperation());
     *
     *  // result == {3,3,3,3,3,3)
     *  \endcode
     *
     *  \see SideBySidePolicy
     *  \see OneToAllPolicy
     *  \see OneToLeftPolicy
     *
     */
    template<class InputIterator1 , class InputIterator2, class OutputIterator , class BinaryFunction>
    void run(InputIterator1 firstBegin,
             const InputIterator1 firstLast,
             InputIterator2 secondBegin,
             const InputIterator2 secondLast,
             OutputIterator result,
             BinaryFunction op)
    {
        doLoop(firstBegin, firstLast, secondBegin, secondLast, result, op);
    }

    template<class InputIterator1, class OutputIterator, class BinaryFunction>
    void run(InputIterator1 firstBegin,
             const InputIterator1 firstLast,
             OutputIterator result,
             BinaryFunction op)
    {
        run(firstBegin, firstLast, firstBegin, firstLast, result, op);
    }



    template<class InputIterator, class OutputIterator, class CombinatorialFunction>
    void combine(InputIterator begin,
                 const InputIterator last,
                 OutputIterator result,
                 CombinatorialFunction op,
                 size_t combinations)
    {
        doLoop(begin, last, result, op, combinations);
    }



};
/*!
 * \}
 */
}


#endif











